// 循环队列
package main

import (
	"fmt"
)

type CycleQueue struct {
	queue    []interface{}
	capacity int //容量
	head     int //对头位置
	tail     int //队尾位置
}

func NewCycleQueue(n int) *CycleQueue {
	if n == 0 {
		return nil
	}
	return &CycleQueue{make([]interface{}, n), n, 0, 0}
}

// 队列为空的条件: (head == tail) 为 true
func (this *CycleQueue) IsEmpty() bool {
	if this.head == this.tail {
		return true
	}
	return false
}

// 队列已满条件: ((tail+1)%capacity == head) 为 true
func (this *CycleQueue) IsFull() bool {
	if this.head == (this.tail+1)%this.capacity {
		return true
	}
	return false
}

// 入队
func (this *CycleQueue) Enqueue(v interface{}) bool {
	if this.IsFull() {
		return false
	}
	this.queue[this.tail] = v
	this.tail = (this.tail + 1) % this.capacity
	return true
}

// 出队
func (this *CycleQueue) Dequeue() interface{} {
	if this.IsEmpty() {
		return nil
	}
	v := this.queue[this.head]
	this.head = (this.head + 1) % this.capacity
	return v
}

func (this *CycleQueue) String() string {
	if this.IsEmpty() {
		return "empty queue"
	}
	result := ""
	var i = this.head
	for true {
		result += fmt.Sprintf("%v ", this.queue[i])
		i = (i + 1) % this.capacity
		if i == this.tail {
			break
		}
	}
	return result
}

func main() {
	// 循环队列 入队
	queue := NewCycleQueue(5)
	queue.Enqueue(1)
	queue.Enqueue(2)
	queue.Enqueue(3)
	queue.Enqueue(4)
	queue.Enqueue(5)
	queue.Enqueue(6)
	fmt.Println(queue) //1 2 3 4

	// 循环队列 出队
	fmt.Println(queue.Dequeue()) //1
	fmt.Println(queue)           //2 3 4
	queue.Dequeue()
	fmt.Println(queue) //3 4
	queue.Dequeue()
	fmt.Println(queue) //4
	queue.Dequeue()
	fmt.Println(queue) //empty queue
}
